n=1000;
u=[1,3,1,5,6,4,5,5,10,6,6,4,14,15,12,17,18,16,12,9,19,23,24,25,26,27,15,29,17,14,10,33,2,35,36,37,1,36,29,34,42,43,44,45,32,47,48,49,50,48,52,8,54,32,56,21,58,17,9,61,61,43,59,28,31,34,67,69,69,23,72,73,17,35,76,12,28,27,80,81,45,83,8,85,86,87,88,23,90,91,92,93,43,95,96,97,24,99,9,101,70,103,61,66,68,107,108,109,110,111,112,113,82,115,46,8,46,103,82,100,122,90,64,32,80,127,128,62,18,131,128,110,134,135,9,137,138,19,140,141,84,115,20,145,108,83,55,149,52,151,152,153,154,155,115,157,33,86,160,25,162,40,124,13,166,73,168,98,63,155,172,56,151,175,173,96,1,139,104,100,182,139,183,73,166,187,188,158,57,12,19,71,194,1,11,180,130,164,200,69,74,203,111,106,206,143,208,23,145,211,212,213,214,215,63,82,218,84,220,107,222,223,187,190,226,206,228,41,230,231,232,217,234,235,236,60,238,239,86,53,242,228,195,245,180,247,109,249,245,146,128,253,129,255,20,119,258,8,197,261,87,143,217,100,266,167,268,269,270,271,272,273,274,228,276,172,278,279,61,262,282,283,173,18,286,47,257,289,290,291,53,233,294,295,296,103,262,98,300,301,302,303,3,64,210,307,308,309,310,311,312,18,314,315,316,317,22,319,320,321,230,323,152,268,26,327,328,329,330,331,332,150,334,335,336,303,338,151,340,341,68,21,321,290,333,252,85,349,350,192,250,353,248,355,187,148,100,25,217,361,76,363,364,365,366,213,368,369,370,371,372,160,80,243,376,377,223,250,42,381,281,260,384,333,248,387,218,228,361,391,208,393,394,395,338,318,357,361,400,389,74,73,92,248,342,407,408,301,320,248,62,413,410,100,416,417,399,419,420,421,422,171,145,425,426,427,428,408,424,431,432,433,128,435,436,293,11,439,61,72,143,293,263,414,335,447,428,449,416,451,90,300,393,455,456,457,117,459,333,70,462,463,464,465,466,163,338,469,370,358,472,473,253,338,476,466,158,43,480,481,482,46,484,231,35,487,488,477,490,491,352,493,494,415,496,143,498,258,500,501,268,354,504,346,506,128,199,88,150,511,512,192,514,348,516,517,313,519,520,521,428,523,446,157,285,527,412,529,530,531,532,212,534,535,106,224,538,11,540,130,542,543,544,33,163,360,548,549,550,551,74,353,554,555,287,557,558,317,214,561,227,115,564,565,438,547,568,163,570,21,152,573,574,575,576,116,513,351,580,465,42,516,555,585,586,587,588,589,590,589,592,548,58,268,573,257,598,599,600,601,602,403,5,245,336,607,608,609,273,611,392,264,614,297,316,617,505,619,406,594,622,123,473,247,626,627,176,75,291,631,150,611,634,498,274,38,638,54,640,464,642,643,644,523,228,647,313,620,650,651,652,653,654,75,96,440,99,659,362,558,662,663,331,473,470,667,77,587,485,265,672,489,674,660,658,215,348,679,680,681,441,382,684,461,686,26,688,478,690,184,692,693,694,695,336,307,51,699,700,118,547,703,704,339,392,707,708,709,615,367,571,713,714,379,716,561,242,115,720,721,579,220,724,321,726,727,728,729,529,731,362,733,734,735,439,737,363,739,740,741,742,417,744,745,746,244,748,203,164,48,752,45,582,413,756,757,758,210,143,761,156,72,764,765,766,767,768,637,604,545,772,220,774,775,776,166,248,779,780,781,782,783,288,324,786,787,788,789,790,791,19,793,561,755,796,797,798,799,800,801,802,803,323,805,639,807,808,334,711,734,790,313,230,336,816,258,266,819,133,691,822,336,824,31,826,827,828,829,830,672,267,833,834,129,836,837,237,839,840,606,829,607,844,845,846,847,848,849,850,851,315,286,806,746,856,857,858,616,860,861,862,438,864,474,326,867,705,248,870,871,872,781,874,875,876,877,878,879,223,511,225,883,873,179,841,887,888,889,282,891,860,893,278,489,194,839,242,816,900,281,902,903,904,905,289,5,235,909,403,501,603,94,900,915,916,917,918,919,79,921,922,923,924,852,649,290,928,399,701,931,932,108,763,935,936,937,938,126,139,442,307,590,358,945,946,947,948,618,506,562,726,753,883,893,244,550,958,657,389,961,1,414,964,131,844,967,968,969,875,971,972,973,216,975,976,438,978,979,980,244,982,714,443,37,986,987,988,989,486,991,935,993,196,995,996,997,998,999,1000];
v=[2,1,4,2,3,7,8,9,4,11,12,13,5,12,16,11,8,19,20,21,22,18,2,24,15,10,28,11,30,31,32,6,34,6,2,6,38,39,40,41,39,17,41,21,46,28,33,13,20,51,50,53,7,55,23,57,46,59,60,34,62,63,64,65,66,67,68,14,70,71,23,62,74,75,23,77,78,79,62,61,82,42,84,28,61,56,27,89,82,52,2,68,94,86,79,92,98,59,100,51,102,56,104,105,106,80,6,59,7,100,5,3,114,5,116,117,118,119,120,121,68,123,124,125,126,45,83,129,130,122,132,133,103,122,136,62,39,139,20,108,142,143,144,87,146,147,148,18,150,29,69,125,102,42,156,124,158,159,102,161,116,163,164,165,85,167,59,169,170,171,101,173,174,109,176,177,178,179,180,181,137,183,184,185,186,44,45,189,190,191,192,193,126,195,196,197,198,199,29,201,202,64,204,205,123,207,127,209,210,210,205,48,204,65,216,217,171,219,189,221,116,12,224,225,36,227,102,229,130,86,24,233,226,163,72,237,194,79,240,241,77,243,244,12,246,169,248,54,250,251,252,163,254,15,256,257,235,259,260,214,262,263,264,265,49,267,229,92,1,52,96,191,128,275,7,277,83,264,280,281,149,234,284,285,188,287,288,266,196,247,292,293,21,21,196,297,298,299,190,160,29,143,304,305,306,225,104,170,122,290,108,313,294,82,89,140,318,157,309,14,322,262,324,325,326,134,208,186,136,191,186,333,196,206,187,337,250,339,48,113,342,343,344,345,346,347,348,280,262,351,352,61,354,261,356,357,358,359,360,149,362,155,160,10,339,367,117,67,237,342,12,373,374,375,323,45,378,379,380,3,382,383,322,385,386,157,388,389,390,242,392,135,289,232,396,397,398,399,96,401,402,403,404,405,406,11,162,409,410,411,412,257,414,415,104,407,418,29,199,6,60,423,424,49,38,185,395,429,430,205,206,365,434,261,403,437,438,274,440,441,442,443,444,445,446,184,448,435,450,125,452,453,454,289,63,291,458,111,460,461,310,74,394,339,275,467,468,222,470,471,127,431,474,475,299,477,478,479,367,473,52,483,235,485,486,406,388,489,379,142,492,122,268,495,157,497,37,499,91,73,502,503,445,505,491,507,508,509,510,209,334,513,64,515,101,327,518,393,69,191,522,418,524,525,526,468,528,280,16,304,356,533,224,245,536,537,298,539,292,541,288,381,316,545,546,547,392,388,191,359,552,553,278,316,556,146,74,559,560,535,562,563,148,344,566,567,138,569,84,571,572,174,469,258,3,577,578,579,356,581,582,583,584,154,541,291,36,543,274,591,101,593,594,595,596,597,37,467,239,17,590,603,604,605,606,502,245,241,610,371,612,613,602,615,616,355,618,576,620,621,119,623,624,625,486,400,628,629,630,311,632,633,607,635,636,637,290,639,257,641,402,591,326,645,646,641,648,649,598,123,483,460,511,655,656,657,658,269,660,661,563,488,664,665,666,534,668,669,670,671,172,673,565,675,676,677,678,671,66,133,682,683,199,685,77,687,585,689,444,691,216,257,368,103,696,697,698,504,170,701,702,228,377,705,706,188,556,248,710,711,712,573,184,715,621,717,718,719,19,162,722,723,244,725,188,328,432,568,730,493,732,568,620,369,736,359,738,620,347,613,304,743,597,150,513,747,468,749,750,751,429,753,754,755,299,522,71,759,760,401,762,763,618,153,294,284,243,769,770,771,19,773,375,574,754,777,778,319,655,217,308,488,784,785,653,245,58,212,319,132,792,470,794,795,223,557,297,592,602,429,408,245,804,319,806,5,709,809,810,811,812,813,814,815,619,817,818,569,820,821,28,823,211,825,620,656,321,756,403,831,832,399,499,835,757,607,838,667,573,841,842,843,106,344,450,520,701,734,107,700,852,853,854,855,586,164,228,859,187,281,466,863,187,865,866,72,868,869,318,292,831,873,29,760,28,614,336,786,880,881,882,681,884,885,886,787,203,485,890,676,892,361,894,895,896,897,898,899,884,901,374,294,433,869,906,907,908,542,910,911,912,913,914,179,627,840,420,474,920,849,280,613,104,925,926,927,418,929,930,601,292,933,934,597,590,188,329,939,940,941,942,943,944,339,610,344,265,949,950,951,952,953,954,955,956,957,290,959,960,359,962,963,731,965,966,839,743,859,970,549,157,944,974,966,679,977,959,730,721,981,314,983,984,985,906,635,327,819,990,823,992,842,994,490,26,671,692,210,836];
w=[14265,16938,18039,16371,721,9026,10772,23686,4853,28397,31158,18924,25067,17678,30040,30689,26979,2774,32006,16236,8019,7434,21210,15686,31895,28053,3380,5518,27075,22608,13625,3242,11851,15119,19853,8576,15830,7408,15700,5334,32734,28895,23397,2565,28044,16237,5584,11492,8658,17362,29074,2291,14280,18495,24215,32198,4939,19817,7152,31924,28628,18770,10325,31681,20885,2393,31453,18888,13529,900,32763,12268,6045,8972,5820,3135,14697,23593,2623,20915,11636,4894,17268,6465,6904,8840,12056,12376,18385,3299,5103,20617,18780,9565,21828,27759,30606,15326,23966,15843,32339,6231,11715,352,10537,20809,19442,2739,17660,18841,3931,7911,13378,24979,994,16239,4442,10043,25108,21141,31521,4571,22378,21794,26582,5320,6844,334,6703,5495,2311,5865,5307,4288,18019,12491,10106,31601,7998,21368,29626,10774,9694,8471,564,19462,18453,24212,18278,17841,22853,13844,12851,30248,19607,25241,8376,13293,7031,12533,22384,3324,5202,499,22154,5657,3475,14787,10633,21851,14554,18599,3358,5112,4734,14555,1857,9042,10566,28105,19862,24898,14946,109,5630,1956,23983,25861,11642,4898,15915,17916,29000,19780,6838,16408,1592,17848,2827,27619,27214,18142,17661,24662,15517,4503,24053,6860,22370,27726,17579,30757,6239,20806,28451,11064,29562,18469,30955,23678,11158,14016,11666,24316,19887,13609,15211,9841,19004,12534,2691,27328,18624,27603,29663,9375,4530,8522,21754,20353,10895,24529,15229,7360,60,24852,9536,1038,15264,28036,4225,23837,7297,5919,22627,28300,30367,22401,6569,7701,11534,23851,7091,11764,18392,5138,31160,13210,32723,13675,2117,13202,23743,27316,13045,3762,16803,20485,20081,11398,872,24985,6827,3833,26037,8343,29014,15173,6669,31525,23720,9244,7463,17327,4691,278,3726,17267,3776,16221,24184,13392,19598,30615,28138,11727,21578,5396,32012,20850,8303,6712,969,16955,4511,11818,20650,13184,28451,24509,2548,6893,12192,18846,27903,20953,1563,959,26585,12749,28463,3586,26906,30802,14989,8233,521,32250,19635,2813,14064,3249,5360,5821,6588,24900,29591,2761,2776,9265,3202,19086,15434,26033,16842,13236,21261,26883,21188,10630,17073,19194,23358,31137,16177,20425,12026,1503,24852,25612,19818,24454,22470,7450,27053,16300,17976,17546,17098,2285,9654,15107,18475,15952,19207,15944,18012,7029,27082,24195,6148,14851,12815,11984,5923,28752,25652,32012,19085,21842,30466,7391,2982,5573,11272,4615,8287,1693,11830,9702,1392,8366,5820,13390,25814,20889,29732,15243,29839,19961,12206,31666,14740,20686,27883,12584,27415,29737,16284,13941,29182,3865,21452,6473,16543,17620,25643,28366,32444,12585,6829,29488,17857,24101,14179,16490,26939,28419,6553,10323,1948,11353,1840,32231,24365,23936,20028,23002,9043,6979,7392,9818,19973,1996,11113,32291,10637,6090,5290,10952,3710,22759,30870,20032,4597,24937,17699,943,8211,21797,16733,885,16057,11180,14024,5756,29829,9136,21755,25789,4109,4023,11129,27412,19291,26627,21970,9285,1960,19904,13818,12621,7515,27503,22761,3309,31812,24210,24947,5748,6164,5784,5480,32716,23840,21770,26863,27335,10582,15094,9247,16811,1407,3996,32479,5883,6838,11351,20223,6279,8232,14797,9366,25013,15629,10841,28829,14609,6886,7608,4556,1298,9207,6643,25524,1071,10759,17804,11293,5154,29015,3819,673,5242,23519,27914,3721,12390,12495,9567,14055,7104,15429,17161,8436,3928,17226,11070,6315,4226,2067,31476,16293,20449,23157,6606,7735,11125,28840,11849,29385,8163,1087,24358,23416,13571,28519,3609,13807,12719,18015,30643,20866,8905,10551,25741,20364,397,18892,22453,19978,1305,25091,26205,14455,27449,5700,9409,23273,17527,58,21593,4972,3939,24008,16191,15774,12062,8270,27874,13451,2348,22556,7148,1737,22138,14390,11632,14551,29613,11850,27991,12723,15534,19182,25612,11705,16242,30238,7525,21443,21005,11252,4308,18557,22521,15785,5839,23560,17059,21196,6012,11730,6454,9920,24225,25268,5035,15995,16586,18765,5393,4732,32187,2205,4376,26893,3095,13540,10468,23738,14929,26300,2831,19216,20691,12405,25343,10138,8557,3504,25449,28440,12288,10559,14373,14082,24682,5434,27444,5436,21939,20837,2318,23578,28281,15297,4145,26262,2712,18288,30694,28879,1566,5581,23125,14533,5485,19915,3531,25427,28337,19854,14666,24940,27780,4679,12369,20889,5600,29268,8684,6578,14148,1432,26367,13532,31017,22550,31695,29122,8103,17108,28881,7447,24418,1774,24246,21579,29627,1784,10678,31884,25140,15001,8220,6655,5923,14437,16401,831,18329,29178,12461,11542,17556,32349,14907,2682,11108,3733,18891,15562,8027,26761,19453,4169,30904,1046,27403,218,5332,9844,31768,17149,13197,6090,10168,3337,3570,20239,6591,7339,4656,12323,17485,13470,28860,14381,537,3756,26305,13366,9213,32228,29132,24070,13762,15645,22709,31550,1580,9642,13776,23222,15945,19038,28244,19480,5109,12994,17163,28093,25521,12949,26170,27847,15781,6532,17106,4991,12786,14122,24792,16880,26684,28490,4882,11460,20087,23115,23027,32349,27377,11763,10183,13879,7584,27239,29217,25212,23725,1891,15493,4072,14400,7605,2129,3039,12685,18687,22001,21708,12574,15788,9026,21692,10338,20275,4934,16954,10870,25227,11017,17260,2098,2286,20434,12142,15223,16081,29325,2542,11702,2850,5240,5384,9668,31427,4364,5475,26844,13383,22830,9356,23285,8171,2966,11665,10821,24535,5758,28641,21013,5269,20111,9315,198,10705,9992,8404,11556,10066,30511,5477,26346,16952,30972,16532,11924,10871,27908,13642,24684,20627,4003,3894,32462,8093,19308,12648,26558,26477,21717,27441,16813,29473,6941,7993,11143,2005,14977,18656,31744,18339,23456,31706,7199,13533,11306,14853,18698,20873,23759,15245,18707,5917,20583,1347,24579,17020,26717,26937,3749,12335,6752,19873,27030,17639,15180,21990,4939,7731,11094,18955,9570,1917,20342,22596,5421,28490,1050,3282,24444,22706,29959,7203,1962,1308,1682,23338,13802,21054,15360,507,210,2132,18233,5289,11815,5279,11700,3683,30443,27681,11934,10957,6820,4758];
m=15;
army=[271,272,116,243,914,65,339,676,971,386,585,439,776,879,391];